package test.algorithm.dp;


import java.util.Arrays;
import java.util.List;

/**
 * @Projectname: algorithm-training-camp
 * @Filename: WordSplit
 * @Author: FANSEA
 * @Date:2024/9/12 11:22
 */
public class WordSplit {
    public static void main(String[] args) {
        String s = "leetcode";
        String[] wordDict = {"leet", "code"};
        List<String> wordDictList = Arrays.asList(wordDict);
        System.out.println(new WordSplit().wordBreak(s, wordDictList));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]表示s的前i个字符是否可以被空格拆分
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // dp[j]为true表示前j个字符组成的字符串存在于字典，如果s[j,i]在wordDict中，则dp[i]为true
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
